package datastructure.hash;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * 0 <= key <= 10^6
 * 最多调用 10^4 次 add、remove 和 contains
 */
public class MyHashSet {

    private LinkedList<Integer>[] buckets;
    private static final int BUCKET_SIZE = 100000;

    public MyHashSet() {
        buckets = new LinkedList[BUCKET_SIZE];
    }

    public void add(int key) {
        if (contains(key)) {
            return;
        }
        int bucketIndex = getBucketIndex(key);
        LinkedList<Integer> bucket = buckets[bucketIndex];
        if (bucket == null) {
            bucket = new LinkedList<>();
            buckets[bucketIndex] = bucket;
        }
        bucket.addFirst(key);
    }

    public void remove(int key) {
        if (!contains(key)) {
            return;
        }
        int bucketIndex = getBucketIndex(key);
        LinkedList<Integer> bucket = buckets[bucketIndex];
        Iterator<Integer> iterator = bucket.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (next.equals(key)) {
                iterator.remove();
                return;
            }
        }
    }

    public boolean contains(int key) {
        int bucketIndex = getBucketIndex(key);
        LinkedList<Integer> bucket = buckets[bucketIndex];
        if (bucket != null) {
            for (Integer i : bucket) {
                if (i != null && i.equals(key)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int bucketIndex = getBucketIndex(1000000);
        System.out.println(bucketIndex);

    }

    private static int getBucketIndex(int key) {
        long hash = key* 100000L;
        return (int)(hash % BUCKET_SIZE);
    }
}
